# LeetCode 1020、飞地的数量
# 一、题目描述
给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。
返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。
示例 1：
img
输入：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出：3
解释：有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。
示例 2：
img
输入：grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出：0
解释：所有 1 都在边界上或可以到达边界。
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 500grid[i][j]的值为0或1
# 二、题目解析
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// https://leetcode.cn/problems/number-of-enclaves/
class Solution {
public int numEnclaves(int[][] grid) {
// 矩阵的行数
int m = grid.length;
// 矩阵的列数
int n = grid[0].length;
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
// i == 0：表示在第 0 行，处于边界位置
// j == 0：表示在第 0 列，处于边界位置
// i == (m - 1)：表示在最后一行，处于边界位置
// j == (n - 1)：表示在最后一列，处于边界位置
// 当格子处于上述任意一种情况的时候，同时还是一个【陆地格子】
// 那么需要基于这个格子继续去搜索
if ((i == 0 || j == 0 || i == (m - 1) || j == (n - 1)) && grid[i][j] == 1){
// 在 dfs 搜索过程中，会不断的把从边界过来的【陆地格子】变成【海洋格子】
dfs(grid, i, j);
}
}
}
// 初始化 result，用来记录飞地的数量
int result = 0 ;
// 经过 dfs 搜索之后的 grid 二维矩阵，从边界过来的【陆地格子】都变成【海洋格子】
// 那么剩下的那些 1 都是飞地
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
if (grid[i][j] == 1){
result++;
}
}
}
return result;
}
public void dfs(int[][] grid, int i, int j) {
// dfs搜索、递归终止条件
// i < 0 ，越界
// j < 0 ，越界
// i >= grid.length ，越界
// j >= grid[0].length ，越界
// grid[i][j] == 0 ，代表当前岛屿无法延伸下去
if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == 0) {
// 直接返回
return ;
}
// 将当前单元格置为 0 ，避免其它格子 dfs 过程中又把它加入到计算中
grid[i][j] = 0;
// 在当前单元格的四个方向开始搜索
// 上：（ 0 ， -1 ）
// 下：（ 0 ， 1 ）
// 左：（ -1 ， 0 ）
// 右：（ 1 ， 0 ）
// dx 为行的方向数组
int dx[] = { -1 , 1 , 0 , 0 };
// dy 为行的方向数组
int dy[] = { 0 , 0 , -1 , 1 };
// 朝着这四个方向开始延伸搜索下去
for (int index = 0; index < 4; ++index) {
// 下一个即将去搜索网格的横坐标
int next_i = i + dx[index];
// 下一个即将去搜索网格的纵坐标
int next_j = j + dy[index];
// 继续搜索
dfs(grid,next_i,next_j);
}
}
}
# 2、C++ 代码
class Solution {
public:
int numEnclaves(vector<vector<int>>& grid) {
// 矩阵的行数
int m = grid.size();
// 矩阵的列数
int n = grid[0].size();
// 从左到右，一行行开始搜索
for (int i = 0; i < m; i++) {
// 从上到下，一列列开始搜索
for (int j = 0; j < n; j++) {
// i == 0：表示在第 0 行，处于边界位置
// j == 0：表示在第 0 列，处于边界位置
// i == (m - 1)：表示在最后一行，处于边界位置
// j == (n - 1)：表示在最后一列，处于边界位置
// 当格子处于上述任意一种情况的时候，同时还是一个【陆地格子】
// 那么需要基于这个格子继续去搜索
if ((i == 0 || j == 0 || i == (m - 1) || j == (n - 1)) && grid[i][j] == 1){
// 在 dfs 搜索过程中，会不断的把从边界过来的【陆地格子】变成【海洋格子】
dfs(grid, i, j);
}
}
}
// 初始化 result，用来记录飞地的数量
int result = 0 ;
// 经过 dfs 搜索之后的 grid 二维矩阵，从边界过来的【陆地格子】都变成【海洋格子】
// 那么剩下的那些 1 都是飞地
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
if (grid[i][j] == 1){
result++;
}
}
}
return result;
}
public:
void dfs(vector<vector<int>>& grid, int i, int j) {
// dfs搜索、递归终止条件
// i < 0 ，越界
// j < 0 ，越界
// i >= board.length ，越界
// j >= board[0].length ，越界
// board[i][j] == X ，不需要继续搜索下去
// board[i][j] == N ，这个格子已经被访问过，不需要继续搜索下去
if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] == 0) {
return;
}
// 将当前单元格置为 0 ，避免其它格子 dfs 过程中又把它加入到计算中
grid[i][j] = 0;
// 在当前单元格的四个方向开始搜索
// 上：（ 0 ， -1 ）
// 下：（ 0 ， 1 ）
// 左：（ -1 ， 0 ）
// 右：（ 1 ， 0 ）
// dx 为行的方向数组
int dx[4] = { -1 , 1 , 0 , 0 };
// dy 为行的方向数组
int dy[4] = { 0 , 0 , -1 , 1 };
// 朝着这四个方向开始延伸搜索下去
for (int index = 0; index < 4; index++) {
// 下一个即将去搜索网格的横坐标
int next_i = i + dx[index];
// 下一个即将去搜索网格的纵坐标
int next_j = j + dy[index];
// 继续搜索
dfs(grid,next_i,next_j);
}
}
};
# 3、Python 代码
class Solution:
def numEnclaves(self, grid: List[List[int]]) -> int:
# 矩阵的行数
m = len(grid)
# 矩阵的列数
n = len(grid[0])
# 从左到右，一行行开始搜索
# 从上到下，一列列开始搜索
for i in range(0 , m ) :
for j in range( 0 , n ):
if ((i == 0 or j == 0 or i == (m - 1) or j == (n - 1)) and grid[i][j] == 1) :
self.dfs(grid,i,j)
res = 0
for i in range(0 , m ) :
for j in range( 0 , n ):
if grid[i][j] == 1 :
res += 1
return res
def dfs(self, grid: List[List[str]], i : int , j : int ) -> None:
# dfs搜索、递归终止条件
# i < 0 ，越界
# j < 0 ，越界
# i >= board.length ，越界
# j >= board[0].length ，越界
# board[i][j] == X ，不需要继续搜索下去
# board[i][j] == N ，这个格子已经被访问过，不需要继续搜索下去
if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == 0 :
return
# 将当前单元格置为 0 ，避免其它格子 dfs 过程中又把它加入到计算中
grid[i][j] = 0
# 在当前单元格的四个方向开始搜索
# 上：（ 0 ， -1 ）
# 下：（ 0 ， 1 ）
# 左：（ -1 ， 0 ）
# 右：（ 1 ， 0 ）
# 朝着这四个方向开始延伸搜索下去
for dx, dy in ((0,1), (1,0), (0,-1), (-1,0)):
# 下一个即将去搜索网格的横坐标
next_i = i + dx
# 下一个即将去搜索网格的纵坐标
next_j = j + dy
self.dfs(grid,next_i,next_j)
# 四、复杂度分析
时间复杂度：O(n×m)，其中 n 和 m 分别为矩阵的行数和列数。深度优先搜索过程中，每一个点至多只会被标记一次。
空间复杂度：O(n×m)，其中 n 和 m 分别为矩阵的行数和列数。主要为深度优先搜索的栈的开销。